package day13;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/13 20:28
 */

/**
 * 你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。
 *
 * 返回 图中已连接分量的数目 。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
 * 输出: 2
 * 示例 2:
 *
 *
 *
 * 输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
 * 输出:  1
 */
public class Solution2 {
    int root[];
    public int countComponents(int n, int[][] edges) {
        root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i]=i;
        }
        int count = 0;
        for (int[] edge : edges) {
            if(find(edge[0])!=find(edge[1])){
                union(edge[0],edge[1]);
                count++;
            }
        }
        return n-count;
    }
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }
}
